package main

import "fmt"

type listNode struct {
	val  int
	Next *listNode
}

func isPalindrome(node *listNode) bool {
	if node == nil || node.Next == nil {
		return false
	}
	flag := true
	var slowPoint *listNode = node
	var QuickPoint *listNode = node

	//如果这个循环一直能进行下去说明链表一直是偶数的，如果停止了之后在判断一下next有没有值就好了
	for QuickPoint.Next != nil && QuickPoint.Next.Next != nil {

		slowPoint = slowPoint.Next
		QuickPoint = QuickPoint.Next.Next
	}

	cur := slowPoint.Next
	var next *listNode
	var pre *listNode
	for cur != nil {
		next = cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	slowPoint.Next = pre

	R := slowPoint.Next
	L := node
	for L.Next != nil && R.Next != nil {
		if L.val != R.val {
			flag = false
		}
		L = L.Next
		R = R.Next
	}

	cur = slowPoint.Next
	var next1 *listNode
	var pre1 *listNode
	for cur != nil {
		next1 = cur.Next
		cur.Next = pre1
		pre1 = cur
		cur = next1
	}
	slowPoint.Next = pre1
	return flag
}
func main() {
	node1 := &listNode{
		1,
		nil,
	}
	node2 := &listNode{
		2,
		nil,
	}
	node3 := &listNode{
		3,
		nil,
	}
	node4 := &listNode{
		2,
		nil,
	}
	node5 := &listNode{
		1,
		nil,
	}

	node1.Next = node2
	node2.Next = node3
	node3.Next = node4
	node4.Next = node5

	palindrome := isPalindrome(node1)
	fmt.Println(palindrome, node1)
}
